"""
牛顿插值代码
"""

import pandas as pd
from scipy.optimize import newton

# 输入数据路径,需要使用Excel格式；
inputfile = '../Data/missing_data.xls'
# 输出数据路径,需要使用Excel格式
outputfile = '../Data/Temp/newton_missing_data_processed.xls'

# 读入数据
data = pd.read_excel(inputfile, header=None, names=['A', 'B', 'C'])
# 判断DataFrame中空值的位置（行，列）
NULL_value_position = []
for j in range(len(data.columns)):
    value_column = data[data.columns[j]].isnull()
    for i in range(len(value_column)):
        if value_column[i] == True:
            NULL_value_position.append((i, j))
print(NULL_value_position)


"""
计算n阶差商：
@brief:   计算n阶差商 f[x0, x1, x2 ... xn]
@param:   xi   所有插值节点的横坐标集合                                                        o
@param:   fi   所有插值节点的纵坐标集合                                                      /   \
@return:  返回xi的i阶差商(i为xi长度减1)                                                     o     o
@notice:  a. 必须确保xi与fi长度相等                                                        / \   / \
           b. 由于用到了递归，所以留意不要爆栈了.                                           o   o o   o
           c. 递归减递归(每层递归包含两个递归函数), 每层递归次数呈二次幂增长，总次数是一个满二叉树的所有节点数量(所以极易栈溢出)                                                                                    
"""
def get_order_diff_quot(xi = [], fi = []):
    if len(xi) > 2 and len(fi) > 2:
         return (get_order_diff_quot(xi[:len(xi) - 1], fi[:len(fi) - 1]) - get_order_diff_quot(xi[1: len(xi)], fi[1: len(fi)])) / float(xi[0] - xi[-1])
    return (fi[0] - fi[1]) / float(xi[0] - xi[1])


"""
@brief:  获得Wi(x)函数;
          Wi的含义举例 W1 = (x - x0); W2 = (x - x0)(x - x1); W3 = (x - x0)(x - x1)(x - x2)
@param:  i  i阶(i次多项式)
@param:  xi  所有插值节点的横坐标集合
@return: 返回Wi(x)函数
"""
def get_Wi(i=0, xi=[]):
    def Wi(x):
        result = 1.0
        for each in range(i):
            result *= (x - xi[each])
        return result
    return Wi


"""
@brief: 获得牛顿插值函数
@
"""
def get_Newton_inter(xi=[], fi=[]):
    def Newton_inter(x):
        result = fi[0]
        for i in range(2, len(xi)):
            result += (get_order_diff_quot(xi[:i], fi[:i]) * get_Wi(i - 1, xi)(x))
        return result

    return Newton_inter


# 自定义列向量插值函数。s为列向量
def Newton_ployinterp_column(s):
    # 剔除空值
    y = s[s.notnull()]
    Nx = get_Newton_inter(y.index, list(y))
    return Nx

# 逐个元素判断是否需要插值
for i in data.columns:
    Newton = Newton_ployinterp_column((data[i]))
    for j in range(len(data)):
        if (data[i].isnull())[j]:
            data[i][j] = Newton(j)

# 输出结果
print(data)
data.to_excel(outputfile, header=None, index=False)
